{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#数组查询\n",
    "def algorithm1(ransomNote, magazine):\n",
    "    ransom_count = [0] * 26\n",
    "    magazine_count = [0] * 26\n",
    "    for x in ransomNote:\n",
    "        ransom_count[ord(x) - ord('a')] += 1\n",
    "    for x in magazine:\n",
    "        magazine_count[ord(x) - ord('a')] += 1\n",
    "    return all(ransom_count[i] <= magazine_count[i] for i in range(26))  # 检查magazine中的字符数是否大于等于ransom，即包含ransom所有信息\n",
    "\n",
    "#Counter查询\n",
    "def algorithm2(ransomNote, magazine):\n",
    "    return not Counter(ransomNote) - Counter(magazine)                   # 字典减法会将对于key值相减，用ransom减去magazine，可得ransom剩余的，有剩余说明magazine没有提取全部信息\n",
    "\n",
    "#字典查询\n",
    "def algorithm3(ransomNote, magazine):\n",
    "    count = {}\n",
    "    for x in magazine:\n",
    "        count[x] = count.get(x,0) +1                 # 收集magazine中所有字符频率，没存入信息时记0\n",
    "    for x in ransomNote:\n",
    "        if x not in count or count[x]==0:            # 比照ransom中字符信息，如果没有包含ransom字符或者数量不够，则报错\n",
    "            return False\n",
    "        count[x] -=1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, False, False)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#示例\n",
    "r1 = 'aabbcc'\n",
    "m1 = 'abc'\n",
    "algorithm1(r1,m1), algorithm2(r1,m1), algorithm3(r1,m1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, True, True)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r2 = 'abc'\n",
    "m2 = 'abcd'\n",
    "algorithm1(r2,m2), algorithm2(r2,m2), algorithm3(r2,m2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
